Casper CBC: Clique Oracle implementations

At a high level, the Clique Oracle can be thought of as looking at a given view and deciding if it is worth attacking with the above adversary in the first place.

First, from the protocol state and given estimate, we construct a graph in the following way:

1. Create a node for each validator in the graph.

2. For each pair of validators, if each validators has a latest message the other with the given estimate and cannot see a message from each other in the future that is not on the given estimate, create an edge between them.

The name of this oracle gives a good clue as to the next step: we search for the biggest clique of validators in the graph. If this clique is greater than 50% by weight, then we can say that we have some degree of fault tolerance on this estimate. Otherwise, the majority of validators are not locked into this estimate, and we cannot say this estimate is safe.

The intuition for this oracle is fairly straight forward: as the estimator functions are determined by validator weight, if the majority of validator weight is locked into seeing a single estimate, this estimate is safe.

Note that this oracle is also a lower bound and only recognizes safety in certain situations.

https://vitalik.ca/general/2018/12/05/cbc_casper.html

Actually detecting all possible situations where the chain becomes stuck on some block (in CBC lingo, the block is “decided” or “safe”) is very difficult, but we can come up with a set of heuristics (“safety oracles”) which will help us detect some of the cases where this happens. The simplest of these is the clique oracle. If there exists some subset V of the validators making up portion p of the total validator set (with p > 1/2) that all make blocks supporting some block B and then make another round of blocks still supporting B that references their first round of blocks, then we can reason as follows:

Because of the two rounds of messaging, we know that this subset V all (i) support B (ii) know that B is well-supported, and so none of them can legally switch over unless enough others switch over first. For some competing B' to beat out B, the support such a B' can legally have is initially at most 1-p (everyone not part of the clique), and to win the LMD GHOST fork choice its support needs to get to 1/2, so at least 1/2 - (1-p) = p - 1/2 need to illegally switch over to get it to the point where the LMD GHOST rule supports B'.

As a specific case, note that the p=3/4 clique oracle offers a 1/4 level of safety, and a set of blocks satisfying the clique can (and in normal operation, will) be generated as long as 3/4 of nodes are online. Hence, in a BFT sense, the level of fault tolerance that can be reached using two-round clique oracles is 1/4, in terms of both liveness and safety.

CBC Casper: Safety Oracle

A clique of validators for some proposition p can be thought of as a set of validators who pairwise see eachother agreeing with p, where there are also no later messages from these validators that are disagreeing with p. A clique can have mulitple layers, although the minimum viable safety oracle will only be 1 − layer deep.

python PoC

# Find biggest set of validators that

# a) each of their latest messages is on the candidate_estimate

# b) each of them have seen from eachother a latest message on the candidate_estimate

# c) none of them can see a new message from another not on the candidate_estimate

# NOTE: if biggest clique can easily be determined to be < 50% by weight, will

# return with empty set and 0 weight.

http://hackingresear.ch/cbc-finality/index.html

(quorum)

We would be happy to find, for an integer qq, a set of validators where each validator from that set

1. Estimates the same consensus value cc.

2. Has acknowledged that (i.e., included in its justification) at least qq other validators from that set has estimated cc.

3. These included validators have kept on estimating the value cc.

Suppose we have the following bipartite graph, where we trace an edge between two validators AA and BB if AA has included a message from BB in its latest justification where BB estimates the same value as AA.

https://github.com/rchain/rchain/blob/16f32316a360d25a3de68605b1a1cb31709b483b/casper/src/main/scala/coop/rchain/casper/SafetyOracle.scala#L13

* "If nodes in an e-clique see each other agreeing on e and can't see each other disagreeing on e,

* then there does not exist any new message from inside the clique that will cause them to assign

* lower scores to e. Further, if the clique has more than half of the validators by weight,

* then no messages external to the clique can raise the scores these validators assign to

* a competing candidate to be higher than the score they assign to e."

* - From https://github.com/ethereum/research/blob/master/papers/CasperTFG/CasperTFG.pdf

* That is unless there are equivocations.

* The fault tolerance threshold is a subjective value that the user sets to "secretly" state that they

* tolerate up to fault_tolerance_threshold fraction of the total weight to equivocate.

* In the extreme case when your normalized fault tolerance threshold is 1,

* all validators must be part of the clique that supports the candidate in order to state that it is finalized.

#Casper